package traverser;

import java.security.NoSuchAlgorithmException;

public class FreqTraverser extends TrieTraverser {
/*
 *Background information about the TrieTraverser:
 * 
 */
	FrequencyCounter fq;
	private final String FCfile = "pageFrequencies.freq";

	// our changes on 11/13
	static PriorityParentQueue toVisit = new PriorityParentQueue();
	static int test2 = 0;

	public FreqTraverser(String startPage, String endPage) {
		super(startPage, endPage);
		fq = new FrequencyCounter(FCfile);
	}

	// Traverse wikipedia, starting at startPage and attempting to find endPage,
	// using a BFS.
	// returns the number of pages accessed prior to finding the target
	public int traverse() {
		int count = 0;
		if (endPage.equals(startPage)) {
			return count;
		}
		count++; // The first page counts
		toVisit.add(startPage, null, fq.frequency(startPage));

		// Idea: pop a page off the queue and add it to the visited list,
		// get all of the links from that page. If the target page
		// is among them, then stop; otherwise, add all the links
		// to the queue and repeat.
		String currentPage = "";
		while ((currentPage = toVisit.pop()) != null) {
			if (visited.contains(currentPage)) {
				System.out.println("Visited contains " + currentPage);
				continue;
			}

			visited.add(currentPage, toVisit.lastParent());
			CacheLinkProcessor lp = new CacheLinkProcessor(currentPage, 123456);
			lp.removeDuplicates();
			lp.knuthShuffle();
			lp.freqSort();

			System.out.println(count + ": Visiting page " + currentPage + " - "
					+ lp.count() + " links.");

			if (lp.count() <= 0) {
				continue;
			}
			
			for (String link : lp.getLinks()) {
				if (link.equals(endPage)) {
					visited.add(endPage, currentPage);
					count++; // The target page counts
					System.out.println(count + ": Found target page " + endPage
							+ ".");
					return count;
				}
				toVisit.add(link, currentPage, fq.frequency(link));
			}
			count++;
		}

		// If we get here, either we have a bug or wikipedia has a closed loop.
		System.out.println("Looks like we exhausted wikipedia.");

		return -1;

	}

	// Test client: traverse from Robot to EMIEW (what's an emiew? good
	// question!)
	public static void main(String[] args) {
		String start = "http://en.wikipedia.org/wiki/Robot";
		String end = "http://en.wikipedia.org/wiki/EMIEW";
		if (args.length >= 2) {
			start = "http://en.wikipedia.org/wiki/" + args[0];
			end = "http://en.wikipedia.org/wiki/" + args[1];
		}

		TrieTraverser test = new TrieTraverser(start, end);

		System.out.println("Found target in " + test.traverse() + " steps.");
		test.printMetrics();
		test.printPath();
	}
}
